/** 
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值
 * 从 1 到 n 互不相同的 二叉搜索树 有多少种
 * 
搜索树：左小右大
dp(i) 1到n二叉树个数
公式 dp(i) += dp(j-1)*dp(i-j)
---------------------------------
【为什么是乘法】
根节点 j 是一个步骤，
计算左子树的可能数量 dp[j-1] 和右子树的可能数量 dp[i-j] 是两个独立的步骤。
因此，总的二叉搜索树数量就是这两个步骤结果数的乘积
---------------------------------
初始化 dp(0)=1 dp(1)=1 
j为头节点 j=1==>n  dp左(j-1)*dp右(i-j)
 * @param {number} n
 * @return {number}
 */

var numTrees = function(n) {
  //dp[0]是推倒dp[1]的前提，dp[n]是最后的结果，所以长度是n+1
  const dp = Array(n+1).fill(0);

  dp[0]=1;
  dp[1]=1;

  //遍历i~n所有方案,记录到dp[i]
  for(let i=2; i<=n; i++) { 
    for(let j=1; j<=i; j++) {
      //当前i个节点，以j为头节点的所有方案数量
      //左子树 j-1(排除自己)个节点，右子树 i-j（剩余节点） 个节点
      dp[i] += dp[j-1]*dp[i-j] 
    }
  }
  return dp[n];
};
/**
 * review1210✅
 */
console.log('不同的搜索二叉树有多少个',numTrees(3)); 
//n = 3 //5

